

class Solution {
    public static void main(String[] args) {
        int [] nums = {0,1,3};
        System.out.println(missingNumber(nums));
    }
    //解法1：
    public static int missingNumber(int[] nums) {
        int sum = 0;
        int addSum = 0;
        int i = 0;
        for (i = 0; i < nums.length; i++) {
            addSum += nums[i];
            sum += i;
        }
        return sum + i - addSum;
    }
    //解法2：排序数组中的搜索问题，首先想到 二分法
    public int missingNumber2(int[] nums) {
        int i =0;
        int j = nums.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[mid] <= mid)  i = mid + 1;
            else j  = mid - 1;
        }
        return i;
    }
}